package com.dyz.swordFingerOffer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author: daiyizheng
 * @date: 2021/6/1 12:56
 * @description:
 */
public class LevelOrder32 {
    public int[] levelOrder(TreeNode32 root) {
        //空树直接返回
        if(root == null) {return new int[0];}
        //初始化空列表存储层序遍历到的各节点
        List<Integer> lists = new ArrayList<>();
        //初始化双端队列进行层序遍历
        Queue<TreeNode32> queue = new LinkedList<TreeNode32>();
        //将根节点加入队列中
        queue.add(root);
        //存储队列中出队的节点
        TreeNode32 node;
        //当队列不空时循环
        while(!queue.isEmpty()){
            //队首第一节点出队
            node = queue.poll();
            //将该节点的值记录到节点值列表中
            lists.add(node.val);
            //当节点存在左/右孩子时，将左/右孩子入队
            if(node.left != null) {queue.add(node.left);}
            if(node.right != null) {queue.add(node.right);}
        }
        //将层序遍历的结果写入返回值数组中
        int size = lists.size();
        int[] ans = new int[size];
        for(int i = 0; i < size; i++){
            ans[i] = lists.get(i);}
        //返回树的层序遍历结果数组
        return ans;
    }
}


class TreeNode32 {
    int val;
    TreeNode32 left;
    TreeNode32 right;

    TreeNode32(int x) {
        val = x;
    }
}